home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / freeWAIS-sf-1.1 / ir / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-12-12  |  18.1 KB  |  649 lines
  1. /* WIDE AREA INFORMATION SERVER SOFTWARE:
  2.    No guarantees or restrictions.  See the readme file for the full standard
  3.    disclaimer.
  4. */
  5.  
  6. /* Copyright (c) CNIDR (see ../COPYRIGHT) */
  7.  
  8.  
  9. /* Hash Table routines
  10.  * for strings based on Common Lisp interface functions.
  11.  *  -brewster
  12.  */
  13.  
  14. /* This hashtable will never grow, rather it just adds entries to the buckets.
  15.  * 
  16.  * The contents are all in one contiguous block so that the contents can be 
  17.  * sorted.  This will cause problems because of the reallocs needed.
  18.  *
  19.  */
  20.  
  21. /* Change log:
  22.  * $Log: hash.c,v $
  23.  * Revision 1.12  1994/12/12  16:23:18  pfeifer
  24.  * typo
  25.  *
  26.  * Revision 1.11  1994/12/12  16:19:38  pfeifer
  27.  * hash_entry_numeric_compare should return int!
  28.  *
  29.  * Revision 1.10  1994/09/02  14:34:21  pfeifer
  30.  * fixed overlapping memory copies
  31.  *
  32.  * Revision 1.9  1994/08/08  10:29:42  pfeifer
  33.  * Fixed the MAX_OCCURANCES - STOP_WORD_FLAG bug
  34.  *
  35.  * Revision 1.8  1994/08/05  07:10:54  pfeifer
  36.  * Release beta 04
  37.  *
  38.  * Revision 1.7  1994/07/22  12:30:05  huynh1
  39.  * left for holidays
  40.  *
  41.  * Revision 1.6  1994/07/13  07:52:36  huynh1
  42.  * Uli
  43.  *
  44.  * Revision 1.5  1994/06/06  11:00:52  huynh1
  45.  * get_hash updated.
  46.  *
  47.  * Revision 1.4  1994/05/20  12:55:57  pfeifer
  48.  * beta
  49.  *
  50.  * Revision 1.3  1994/03/08  20:37:44  pfeifer
  51.  * Patchlevel 04
  52.  *
  53.  * Revision 1.2  1994/02/14  10:49:47  huynh1
  54.  * new code for field concept added.
  55.  *
  56.  * Revision 1.1  1993/02/16  15:05:35  freewais
  57.  * Initial revision
  58.  *
  59.  * Revision 1.9  92/05/06  17:27:38  jonathan
  60.  * Added cast for htable->contents malloc.
  61.  * 
  62.  * Revision 1.8  92/02/21  11:06:53  jonathan
  63.  * Added header, RCSIdent.
  64.  * 
  65.  * Revision 1.7  92/02/16  12:37:57  jonathan
  66.  * Changed bzero's to memset's.
  67.  * 
  68.  * Revision 1.6  92/02/12  13:20:08  jonathan
  69.  * Added "$Log" so RCS will put the log message in the header
  70.  * 
  71. */
  72.  
  73. /* Cool things we could do from here:
  74.      A) Use a signature to see if the word is in the hashtable, so that
  75. get_hash will return NULL very quickly for the new words.  This will reduce
  76. the number of times a whole bucket must be searched.  This might not help
  77. much since the file that I was indexing had 8M words, and only 350k
  78. different words, so there are 1 NULL in 30 requests expected. Therefore,
  79. unless searching down a list of buckets takes a long time, this is not a
  80. big problem.  The only case I can think of is if it induces paging.
  81.     B) Since the most recently accessed entry of the hashtable is at the
  82. front, we can sort the hashtable entries so that the heads of all the
  83. buckets are clumped, so that hopefully these will stay in memory, and the
  84. infrequently used ones would move to the paged out space.
  85. */
  86.  
  87. #ifndef lint
  88. static char *RCSid = "$Header: /usr/local/ls6/src+data/src/freeWAIS-sf/ir/RCS/hash.c,v 1.12 1994/12/12 16:23:18 pfeifer Exp $";
  89. #endif
  90.  
  91. #include "cdialect.h"
  92. #include "cutil.h"
  93. #include "hash.h"
  94. /* #include <string.h> */
  95. #include "panic.h"
  96.  
  97. #define ALIGNMENT_SIZE 4 /* the word size to align elements of the contents on */
  98.  
  99.  
  100. #ifdef NEW_WEIGHT /* tung, 5/94 */
  101. #include "irfiles.h" 
  102. #include "irhash.h"             /* MAX_OCCURANCES */
  103. #endif
  104.  
  105. hashtable*
  106. make_hashtable (number_of_buckets, number_of_elements, element_size)
  107.      long number_of_buckets;
  108.      long number_of_elements;
  109.      long element_size;
  110. {
  111.   hashtable *htable = (hashtable *)s_malloc(sizeof(hashtable));
  112.  
  113.   if(number_of_buckets > 0)
  114.     htable->number_of_buckets = number_of_buckets;
  115.   else
  116.     htable->number_of_buckets = DEFAULT_NUMBER_OF_BUCKETS;
  117.  
  118.   htable->buckets_mask = htable->number_of_buckets - 1;
  119.  
  120.   if(element_size > 0){
  121.     htable->element_size = element_size;
  122.   }
  123.   else
  124.     return(NULL);
  125.   
  126.   htable->number_of_elements = 0;
  127.  
  128.   if(number_of_elements > 0)
  129.     htable->max_number_of_elements = number_of_elements;
  130.   else
  131.     htable->max_number_of_elements = DEFAULT_NUMBER_OF_ELEMENTS;
  132.  
  133.   htable->buckets
  134.     = (long*)s_malloc(sizeof(long) * htable->number_of_buckets);
  135.   /* this depends on -1L to be made up of -1 characters */
  136.   memset(htable->buckets, -1, sizeof(long) * htable->number_of_buckets);
  137.  
  138.   htable->contents 
  139.     = (hash_entry*)s_malloc(htable->max_number_of_elements * 
  140.                 htable->element_size);
  141.   return(htable);
  142. }
  143.  
  144.  
  145. /*----------------------------------------------------------------- */
  146.  
  147. /* returns a hashcode for a string.  
  148.  * key is a string that is assumed to be downcased (if appropriate),
  149.  * function is a number from 0 to 20 that are fairly independent hash 
  150.  *    functions.
  151.  */
  152.  
  153.  
  154. /*===========================*
  155.  *===  Hashing Functions  ===*
  156.  *===========================*/
  157.  
  158.  
  159. /*___________________________________________________________________________*/
  160.  
  161. /* Date: Fri, 13 Dec 91 16:28:53 EST
  162.    From: Henry Massalin <henry@cs.columbia.edu> */
  163.  
  164. #define reg    register
  165.  
  166. hash(s)
  167. reg    unsigned char    *s;
  168. {
  169.   reg    int        c;
  170.   reg    unsigned long    h = 0;
  171.   extern    unsigned long    RandHash[];
  172.  
  173.   if((h = (unsigned long)*s++) == 0)
  174.     return(h);
  175.   while((c = *s++) != 0)
  176.     h += RandHash[ 0xFF & ((h >> 24) ^ c )];
  177.   return(h);
  178. }
  179.  
  180. /*___________________________________________________________________________*/
  181.  
  182. /*
  183.  * Almost any random permutation will work.  Of course, now that I've
  184.  * picked this one, everyone else must use it also, to be consistent.
  185.  *
  186.  * This array is constructed from four independent permutations of the
  187.  * integers 0..255.  A different permutation in each of the bytes.
  188.  */
  189. unsigned long
  190.     RandHash[256] = {
  191.     0x4BEF74B7,0x7FE1F5A6,0xB4C08BF6,0xC2CF0CD0,
  192.     0x788E2A29,0xB043B6B9,0x5B56C90C,0x324D8FE7,
  193.     0x8D9C854A,0xCAE06AC8,0x902076A1,0x949EAA31,
  194.     0xDC070A08,0xF7499B6D,0x17883EAA,0x22A65A35,
  195.     0x34FC6407,0x8322F367,0xD105BB0F,0xD8A29526,
  196.     0x8A1B708A,0xBE85B1E1,0xC66AC334,0xC1B13A1C,
  197.     0xEDF644E4,0x3EA3806C,0x2732D31D,0xEBF504A9,
  198.     0x08BB2B52,0x4775992C,0x3C0B8CF7,0x5FA0AEA2,
  199.     0x7616D761,0x66AA86DB,0xC73305C0,0x09E6EA99,
  200.     0xC9789DD6,0xF47340F1,0x3941303E,0x7542233A,
  201.     0xE0812ED1,0xFF2E54FE,0x07B887EB,0x68CD0E93,
  202.     0xB124C17F,0xD01A9C5B,0x96B490ED,0xA7CAE5FC,
  203.     0x18D41F37,0x6E8DA1BC,0x9B631940,0x35ABCFD4,
  204.     0xACA1FB0A,0x2F71B921,0x6F10A747,0xA6680796,
  205.     0x01F12271,0xFDBE0378,0x02F0FF79,0xEC3FF2D2,
  206.     0x84485C9C,0x60BF9113,0x98CC35E3,0xAA2A8D4D,
  207.     0xA5CBA2E9,0xF0AE1EF2,0x990118E2,0x64A966F5,
  208.     0x8595490D,0x7E9B4391,0xE8311B7D,0x2474BCBF,
  209.     0x19D6E286,0xDFD32D5C,0xAB5116CA,0x7D72D6D5,
  210.     0x0BF44F5E,0x6170B3D3,0x2C471CC2,0x2EFD1118,
  211.     0x8C878836,0x62FE52E0,0x2B8C1277,0x2ACEBDEC,
  212.     0xB2E8A8A3,0x30B757AE,0x708BBA8D,0x501EF654,
  213.     0x49A7EF1E,0xFE7636AD,0xB54BBE4F,0x1ADBDB8C,
  214.     0x72E24DD9,0xF68A2517,0xF56FEEDF,0x5A7EB75D,
  215.     0xD606F9E6,0xC32526B8,0x5EB613F3,0x0C08CBDE,
  216.     0x8B965E59,0xB361EB75,0x3FADE465,0xB8FFD16F,
  217.     0x26442988,0x00D2D830,0x3D58FE41,0x3B386E44,
  218.     0x1297E914,0xAFC11083,0xC5EBE8B6,0x15A49ECD,
  219.     0xF950C263,0xA0DA0982,0x4CBDF101,0xE227F77E,
  220.     0x556DB8DA,0xA1BA2125,0x1E3BD409,0xFCF25155,
  221.     0x110A983B,0x7B7F1A4C,0xE7FB4C69,0xC8994E1F,
  222.     0x586C4A42,0x5C1FAF2F,0xAD777D48,0x9186696B,
  223.     0xD52181B4,0xE94C39EF,0x9EDEB2FF,0x802FDA20,
  224.     0xA228D902,0x52BC7CFD,0x53DD47AC,0x6D12D25F,
  225.     0xCE1D6D8F,0xF12C8E2B,0xDD5700C1,0x9A402851,
  226.     0x386E53D7,0x0DF88281,0x4A55CDC4,0x653692B0,
  227.     0x203CAC8E,0x747C6164,0xC47A02B2,0x1B4FC82D,
  228.     0xF8934B7A,0x36A82CB5,0x690CD080,0x2800A524,
  229.     0x1C045D0E,0xBF09CAF0,0x8814ABB3,0xE3D0776A,
  230.     0x219AA6D8,0xCC375653,0xFA2327A8,0x57F75F27,
  231.     0x732DA903,0x8F696738,0x3A453223,0xDA1C9F32,
  232.     0xCF90152A,0x0F64BFF4,0xD7533FA5,0x8E7D55DC,
  233.     0xBC598998,0x45110DBA,0x4D92E6FB,0x7746C01A,
  234.     0x951348A0,0xBBFA7E9B,0x055EAD7B,0x06B36BBB,
  235.     0x0EE31D97,0x37297F11,0xEF529450,0x51C6E168,
  236.     0x1F67C63F,0x6B023443,0x449F5BFA,0x48C39A4B,
  237.     0xD30E426E,0x0ADFE31B,0x467B6085,0x7CC49676,
  238.     0x140DFA60,0xE16B7274,0x235AEC05,0xD2D7DCC6,
  239.     0x13946212,0x339D2462,0xFB82F8EE,0xB6197970,
  240.     0xBD0F3C9D,0xE64E3B28,0xE4B07A87,0x54C92F95,
  241.     0x6CC583AB,0xD4182015,0x86DC755A,0xA930A333,
  242.     0x82B273EA,0x923EED7C,0xF354A02E,0xEEEEA439,
  243.     0x1D89089A,0xD9EDDEE8,0x1017B504,0xA45CB0C7,
  244.     0x93C7E0A4,0x43D95858,0xDB654594,0x31D578CF,
  245.     0xCDF98489,0xB915C7F9,0x67846FE5,0x04D150AF,
  246.     0x5DF314DD,0xCB911772,0xA8627156,0x258FC573,
  247.     0xEAA5E79F,0x633D4119,0x793501C9,0x7AD80F0B,
  248.     0x4E5DF04E,0x97AF6884,0xAE3A9745,0xA3ACF48B,
  249.     0x16398A10,0xDE8346C3,0x42C20606,0x03EAB4B1,
  250.     0x8798FDCC,0x9CE4FC22,0x81B5DD3D,0x563431BE,
  251.     0x2D799349,0xF2036C92,0xB7E97B3C,0x71E559C5,
  252.     0x5960C4BD,0x295B63F8,0xBA5F0B57,0xE5B93DCE,
  253.     0x6A4ACC90,0x89EC6516,0x4180D566,0x40263300,
  254.     0x9DE738CB,0x4F2B3746,0x9F66DF9E,0xC0C8CEA7
  255. };
  256.  
  257. /*___________________________________________________________________________*/
  258.  
  259. /*
  260.  * Create permutations
  261.  */
  262. #if 0
  263. #define N        256
  264. #define    ulong        unsigned long
  265.  
  266. main()
  267. {
  268.     int     i, j;
  269.     ulong    p[N], q[N];
  270.  
  271.     permute(p);
  272.     for(i=3; --i >= 0; ) {
  273.         permute(q);
  274.         for(j=N; --j >= 0; )
  275.             p[j] = (p[j] << 8) + q[j];
  276.     }
  277.  
  278.     printf("ulong    RandHash[%d] = {", N);
  279.     for(i=0; i<N; i++)
  280.         printf("%s0x%08X", ((i&3) ? "," : "\n\t"), p[i]);
  281.     printf("\n};\n\n");
  282. }
  283.  
  284. permute(p)
  285. ulong    *p;
  286. {
  287.     int     i, r, t;
  288.  
  289.     /* initialize array */
  290.     for(i=N; --i >= 0; )
  291.         p[i] = i;
  292.  
  293.     /* generate random permutation */
  294.     for(i=N; --i >= 0; ) {
  295.         r = (i * (random() & 0xFFFF)) >> 16;
  296.         t = p[r]; p[r] = p[i]; p[i] = t;
  297.     }
  298. #if 0
  299.     /* make sure there are no cycles of len < N */
  300.     for(i=N; --i >= 0; ) {
  301.     }
  302. #endif
  303. }
  304.  
  305. #endif
  306.  
  307. /* --------------------------- */
  308.  
  309. #ifdef UNUSED
  310.  
  311. /* courtesy ses@ccgr.technion.ac.il, but it turns out in
  312.    informal timings that it increases the index time.  sigh. */
  313.  
  314. static char coeff[] = {
  315.         61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  316.         61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  317.         61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  318.         61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  319.         61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  320.         61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  321.         61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  322.         61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1};
  323.  
  324.  
  325. long hash_code(key, function)
  326.      char *key;
  327.      long function;
  328. {
  329.   register char *foo;
  330.   register long hash = 0;
  331.   register int l;
  332.  
  333.   for(l=function,foo=key;l<sizeof(coeff) && *foo ;l++)
  334.     hash = hash + (*(foo++) * coeff[l]);
  335.  
  336.   return(hash);
  337. }
  338.  
  339. #endif /* def UNUSED   */
  340.  
  341.  
  342. /*----------------------------------------------------------------- */
  343. #ifdef NEW_WEIGHT /* tung, 5/94 */
  344. extern long bucket_ids_doc_array[]; /* defined in weight.c */
  345. extern long number_of_bucket_ids;   /* defined in irtfiles.c */
  346. #endif
  347.  
  348. #define HASHTABLE_GROW_FACTOR 4
  349.  
  350. hash_entry *put_hash(key, htable, element)
  351.      char *key;
  352.      hashtable *htable;
  353.      hash_entry *element;
  354. {
  355.   /* allocate the entry out of the contents area, then add the entry to 
  356.      the head of the bucket list. */
  357.  
  358.   /* old long bucket_number = hash_code(key, 0) & htable->buckets_mask; */
  359.   long bucket_number = hash((unsigned char*)key) & htable->buckets_mask;
  360.   long old_bucket_value =  (htable->buckets)[bucket_number];
  361.   long new_bucket_value = htable->number_of_elements++;
  362.   hash_entry *entry_header;
  363.  
  364.   if(new_bucket_value >= htable->max_number_of_elements){
  365.     long new_size = 
  366.       HASHTABLE_GROW_FACTOR * htable->max_number_of_elements * 
  367.     htable->element_size;
  368.     
  369.     waislog(WLOG_LOW, WLOG_INFO, 
  370.         "Expanding hashtable from %ld bytes to %ld bytes address %ld...",
  371.        htable->max_number_of_elements * htable->element_size ,
  372.        new_size, htable->contents);
  373.     htable->max_number_of_elements *= HASHTABLE_GROW_FACTOR;
  374.     htable->contents = (hash_entry*)s_realloc(htable->contents, new_size);
  375.     if(NULL == htable->contents)
  376.       panic("Out of virtual memory.");
  377.   }
  378.   entry_header = &(htable->contents)[new_bucket_value];
  379.   memcpy((char *)entry_header, (char *)element, htable->element_size);
  380.   /* printf("Writing key: '%s' into index %ld\n", key, new_bucket_value); */
  381.   strncpy(entry_header->key, key, MAX_KEY_SIZE + 1); 
  382.   entry_header->next = old_bucket_value;
  383.  
  384.   (htable->buckets)[bucket_number] = new_bucket_value;
  385. #ifdef NEW_WEIGHT /* tung, 5/94 */
  386.   bucket_ids_doc_array[number_of_bucket_ids++] = new_bucket_value;
  387. #endif
  388.   return(entry_header);
  389. }
  390.  
  391. /*----------------------------------------------------------------- */
  392.  
  393. /* returns a pointer to the element stored or NULL if none. */
  394. hash_entry *get_hash (key, htable)
  395.      char *key;
  396.      hashtable *htable;
  397. {
  398.   /* this looks up the value in the bucket and puts it at the head of the 
  399.      bucket. */
  400.  
  401.   /* old long bucket_number = hash_code(key, 0) & htable->buckets_mask; */
  402.   long bucket_number = hash((unsigned char*)key) & htable->buckets_mask;
  403.   long old_bucket_value =  (htable->buckets)[bucket_number];
  404.  
  405.   long next_contents_index = old_bucket_value;
  406.  
  407.   while(next_contents_index != -1){
  408.     /* keep looking down the list for the right value */
  409.     if(0 == strcmp((htable->contents)[next_contents_index].key, 
  410.            key)) {
  411. #ifdef NEW_WEIGHT /* tung, 5/94 */
  412.       if((htable->contents)[next_contents_index].number_of_occurances < MAX_OCCURANCES) {
  413.     if((htable->contents)[next_contents_index].occurances_in_doc == 0) {
  414.       bucket_ids_doc_array[number_of_bucket_ids++] = next_contents_index;
  415.     }
  416.       }
  417. #endif
  418.       /* found it */
  419.       return(&(htable->contents)[next_contents_index]);
  420.     }
  421.     else 
  422.       next_contents_index = (htable->contents)[next_contents_index].next;
  423.   }
  424.   return(NULL);
  425. }
  426.   
  427.  
  428. /*----------------------------------------------------------------- */
  429.  
  430. boolean clr_hashtable (htable)
  431.      hashtable *htable;
  432. {    
  433.   htable->number_of_elements = 0;
  434.   memset(htable->buckets, -1, sizeof(long) * htable->number_of_buckets);
  435.   return(true);
  436. }
  437.  
  438. /*----------------------------------------------------------------- */
  439.  
  440. /* removes contents and free's memory for the hastable.   
  441.    returns true if successful, false otherwise */
  442. boolean free_hashtable(htable)
  443.      hashtable *htable;
  444. {
  445.   s_free(htable->contents);
  446.   s_free(htable->buckets);
  447.   s_free(htable);
  448.   return(true);
  449. }
  450.  
  451. /*----------------------------------------------------------------- */
  452.  
  453. /* returns the number of elements in the hashtable */
  454. long hashtable_count(htable)
  455.      hashtable *htable;
  456. {
  457.   return(htable->number_of_elements);
  458. }
  459.  
  460. /*----------------------------------------------------------------- */
  461.  
  462.  
  463. static int hash_entry_compare _AP((hash_entry*i,hash_entry* j));
  464.  
  465. static int hash_entry_compare(i,j)
  466. hash_entry *i;
  467. hash_entry *j;
  468. {
  469.   return(strcmp(i->key, j->key));
  470. }
  471.  
  472.  
  473. boolean sort_hashtable(htable)
  474.      hashtable *htable;
  475. {
  476.   qsort(htable->contents,
  477.     htable->number_of_elements,
  478.     (size_t)sizeof(hash_entry),
  479.     hash_entry_compare);
  480.   return(true);
  481. }
  482.  
  483.  
  484. #ifdef FIELDS /* tung, 1/94 */
  485. static int hash_entry_numeric_compare _AP((hash_entry*i,hash_entry* j));
  486.  
  487. static int hash_entry_numeric_compare(i,j)
  488. hash_entry *i;
  489. hash_entry *j;
  490. {
  491.   int i_sign = 1;
  492.   int j_sign = 1;
  493.   char* i_key = i->key;
  494.   char* j_key = j->key;
  495.   double i_number, j_number;
  496.   
  497.   if(i_key[0] == '-') {
  498.     i_sign = -1;
  499.     i_key = i_key + 1;
  500.   }
  501.   if(j_key[0] == '-') {
  502.     j_sign = -1;
  503.     j_key = j_key + 1;
  504.   }
  505.  
  506.   i_number = atof(i_key) * i_sign;
  507.   j_number = atof(j_key) * j_sign;
  508.   if(i_number > j_number) return(1);
  509.   else if(i_number < j_number) return(-1);
  510.   else return(0);
  511. }
  512.  
  513. boolean sort_hashtable_numeric(htable)
  514.      hashtable *htable;
  515. {
  516.   qsort(htable->contents,
  517.     htable->number_of_elements,
  518.     (size_t)sizeof(hash_entry),
  519.     hash_entry_numeric_compare);
  520.   return(true);
  521. }
  522. #endif
  523.  
  524. /*----------------------------------------------------------------- */
  525. /* print routines */
  526.  
  527.  
  528. static void print_content_element(index, htable)
  529.      long index;
  530.      hashtable *htable;
  531. {  
  532.   printf("  Index: %ld, key: '%s', Next index %ld\n", 
  533.      index, (htable->contents[index]).key, 
  534.      (htable->contents[index]).next);
  535. }
  536.  
  537. void print_bucket(bucket, htable)
  538.      long bucket;
  539.      hashtable *htable;
  540. {
  541.   long next_contents_index = (htable->buckets)[bucket];
  542.  
  543.   printf(" Bucket: %ld\n", bucket);
  544.   while(next_contents_index != -1){
  545.     hash_entry * entry_header = &(htable->contents)[next_contents_index];
  546.     print_content_element(next_contents_index, htable);
  547.     next_contents_index = entry_header->next;
  548.   }
  549.   return;
  550. }
  551.  
  552. long bucket_length(bucket, htable)
  553.      long bucket;
  554.      hashtable *htable;
  555. {
  556.   long next_contents_index = (htable->buckets)[bucket];
  557.   long answer = 0;
  558.   while(next_contents_index != -1){
  559.     answer++;
  560.     next_contents_index = ((htable->contents)[next_contents_index]).next;
  561.   }
  562.   return(answer);
  563. }
  564.  
  565. static int bucket_length_compare _AP((long*i,long* j));
  566.  
  567. static int bucket_length_compare(i,j)
  568. long *i;
  569. long *j;
  570. {
  571.   return((*j) - (*i));
  572. }
  573.  
  574. void analyze_hashtable_distribution(htable)
  575.      hashtable * htable;
  576. {
  577.   long count = 0;
  578.   long max_length = 128;
  579.   long *bucket_length_array = (long *)malloc(sizeof(long) * max_length);
  580.   memset((char*)bucket_length_array, 0, (sizeof(long) * max_length));
  581.  
  582.   waislog(WLOG_LOW, WLOG_INFO, "--Hashtable Analysis--");
  583.   waislog(WLOG_LOW, WLOG_INFO, "Number of buckets: %ld",
  584.       htable->number_of_buckets);
  585.   waislog(WLOG_LOW, WLOG_INFO, "Number of allocated elements %ld",
  586.       htable->number_of_elements);
  587.   waislog(WLOG_LOW, WLOG_INFO, "Max number of elements %ld",
  588.       htable->max_number_of_elements);
  589.  
  590.   while(count < htable->number_of_buckets){
  591.     long length = bucket_length(count, htable);
  592.     if(length > max_length){  /* too small, start again */
  593.       max_length *= 2;
  594.       free((char*)bucket_length_array);
  595.       bucket_length_array = (long *)malloc(sizeof(long) * max_length);
  596.       memset((char*)bucket_length_array, 0, (sizeof(long) * max_length));
  597.       count = 0;
  598.     }
  599.     else{
  600.       bucket_length_array[length]++;
  601.       count++;
  602.     }
  603.   }
  604.   /* print the buckets */
  605.   for(count = 0; count < max_length; count++){
  606.     if(bucket_length_array[count] > 0){
  607.       waislog(WLOG_LOW, WLOG_INFO, "Length %4ld, number of buckets: %5ld.",
  608.           count, bucket_length_array[count]);
  609.     }
  610.   }
  611.   free((char*)bucket_length_array);
  612. }
  613.  
  614. void print_hashtable(htable)
  615.      hashtable * htable;
  616. {
  617.   long count;
  618.   printf("Number of buckets: %ld\n",  htable->number_of_buckets);
  619.   printf("Bucket mask %ld\n", htable->buckets_mask);
  620.   printf("Element Size %ld\n", htable->element_size);
  621.   printf("Number of allocated elements %ld\n", htable->number_of_elements);
  622.   printf("Max number of elements %ld\n", htable->max_number_of_elements);
  623.   
  624.   printf("\nContents:\n");
  625.   for(count = 0; count < htable->number_of_elements; count++){
  626.     print_content_element(count, htable);    
  627.   }
  628.   printf("\nBuckets:\n");
  629.   for(count = 0; count < htable->number_of_buckets; count++){
  630.     if((htable->buckets)[count] != -1)
  631.       print_bucket(count, htable);    
  632.   }
  633. } 
  634.  
  635. /* for saber trials:
  636.  
  637. foo(){
  638. hashtable *htable;
  639. hash_entry entry;
  640. htable = make_hashtable(0, 0, sizeof(hash_entry));
  641. print_hashtable(htable);
  642. put_hash("food", htable, &entry);
  643. print_hashtable(htable);
  644. *get_hash("food", htable);
  645. put_hash("food", htable, &entry);
  646. print_hashtable(htable);
  647. }
  648. */
  649.